#include <stdio.h>

void reset(int *nums1, int *nums2, int length)
{
    for (int i = 0; i < length; i++) {
        nums1[i] = nums2[i];
    }
}

void printNums(int *nums, int length) 
{
    for (int i = 0; i < length; i++) {
        printf("%d ", nums[i]);
    }
    putchar('\n');
}

//插入：

void InsertSort_1(int *nums, int length) 
{
    printf("%s:\n", __func__);
    for (int i = 1; i < length; i++) { //第一个元素开始
        for (int j = 0; j < i; j++)  //从前开始比较 //这时的j=0即j=i-1;
            if (nums[i] < nums[j]) { //定位
                int tmp = nums[i];
                int k;
                for (k = i; k > j; k--) {
                    nums[k] = nums[k-1]; // 向后移动
                }       
            nums[j] = tmp; //此时正好k==j;
            break; //此时退出
        }
    }
    printNums(nums, length);
}

void InsertSort(int *nums, int length) 
{
    printf("%s:\n", __func__);
    for (int i = 1; i < length; i++) {//第二个元素开始
        int tmp = nums[i]; //暂存防止覆盖
        int j;
        for (j = i; j > 0 && nums[j-1] > tmp; j--) {
            nums[j] = nums[j-1];
        }
        nums[j] = tmp; //此时j-- 刚刚好
    }
    printNums(nums, length);
}

void binInsertSort(int *nums, int length) 
{
    printf("%s:\n", __func__);
    for (int i = 1; i < length; i++) {//第二个元素开始
        int low = 0; 
        int hight = i-1; //二分查找位置
        while (low <= hight) {
            int mid = (low + hight)/2;
            if (nums[i] > nums[mid]) low = mid + 1;
            else if (nums[i] < nums[mid]) hight = mid-1;
            else 
                break;
        }
        int tmp = nums[i];
        for (int j = i; j > low; j--) {
            nums[j] = nums[j-1];
        }
        nums[low] = tmp;
    }
    printNums(nums, length);
}

void ShellSort_1(int *nums, int length, int step)
{
    printf("%s:\n", __func__);
    for (int i = 0; i < length; i++) {  
        for (int j = i + step; j < length; j+=step) {
            for (int k = i; k < j; k+=step) {  //找到位置
                if (nums[j] < nums[k]) {
                    int tmp = nums[j]; //暂存
                    for (int l = j; l > k; l-=step) {
                        nums[l] = nums[l-step];
                    }
                    nums[k] = tmp;
                    break;
                }
            }
        }
    }
}

void ShellSort(int *nums, int length, int step)
{
    printf("%s:\n", __func__);
    for (int i = 0; i < length; i++) {  //感觉可以配合step优化循环次数
        for (int j = i + step; j < length; j+=step) {
            int tmp = nums[j];
            int k;
            for (k = j; k > 0 && nums[k-step] > tmp; k-=step) {
                nums[k] = nums[k-step];
            }
            nums[k] = tmp;
        }
    }
}

//交换：

void swap (int *a, int *b) 
{
    int tmp = *a; 
    *a = *b;
    *b = tmp;
}

void BubbleSort_1(int *nums, int length) 
{
    printf("%s:\n", __func__);
    for (int i = 1; i < length; i++) {
        for (int j = 0; j < length-i; j++) {
            if (nums[j] > nums[j+1]) {
                swap(&nums[j], &nums[j+1]);
            }
        }
    }
    printNums(nums, length);
}

void BubbleSort(int *nums, int length) 
{
    printf("%s:\n", __func__);
    int flag = 1;
    for (int i = 1; i < length && flag == 1; i++) { //flag 可以提前结束循环
        for (int j = 0; j < length-i; j++) {
            flag = 0;
            if (nums[j] > nums[j+1]) {
                flag = 1;
                swap(&nums[j], &nums[j+1]);
            }
        }
    }
    printNums(nums, length);
}

int partition(int *nums, int left, int right) 
{
    int tmp = nums[left];
    while (left < right) {
        while (nums[right] > tmp && left < right) {
            right--;
        }
        if (left < right) { //注意此时的++操作只有left!=right时执行
            nums[left] = nums[right];
            left++;
        }
        while (nums[left] < tmp && left < right) {
            left++;
        }
        if (left < right) {
            nums[right] = nums[left];
            right--;
        }
    }
    nums[left] = tmp;//此时left = right;
    return left;
}

void QuickSort(int *nums, int left, int right) 
{
    if (left < right) {
        int index = partition(nums, left, right);
        QuickSort(nums, left, index-1);
        QuickSort(nums, index+1, right);
    }
}

int main(void) 
{
    //nums1 作为输入  nums2备份
    int nums1[10] = {10, 9, 8, 4, 5, 6, 7, 3, 2, 1};
    int nums2[10] = {10, 9, 8, 4, 5, 6, 7, 3, 2, 1};
    printf("原来：\n");
    printNums(nums1, 10);
    InsertSort_1(nums1, 10); //未调节的插入排序 
    reset(nums1, nums2, 10);
    binInsertSort(nums1, 10);
    reset(nums1, nums2, 10);
    InsertSort(nums1, 10); 
    reset(nums1, nums2, 10);
    BubbleSort_1(nums1, 10);
    reset(nums1, nums2, 10);
    BubbleSort(nums1, 10);
    reset(nums1, nums2, 10);
    
    int step[3] = {5, 3, 1};
    
    for (int i = 0; i < 3; i++) {
        ShellSort_1(nums1, 10, step[i]);
        printNums(nums1, 10);
    }
    reset(nums1, nums2, 10);
    
    for (int i = 0; i < 3; i++) {
        ShellSort(nums1, 10, step[i]);
        printNums(nums1, 10);
    }
    reset(nums1, nums2, 10);
    
    printf("QuickSort:\n");

    QuickSort(nums1, 0, 9);
    printNums(nums1, 10);
    reset(nums1, nums2, 10);
    
    return 0;
}